package question.solution39;

import question.SolutionTemplate;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution39 implements SolutionTemplate {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        int[] counts = new int[candidates.length];
        List<List<Integer>> result = new ArrayList<>();
        for(int candidateCount =0;;candidateCount++){
            counts[candidates.length-1] = candidateCount;
            boolean probeSuccess = probe(candidates, counts, target, candidates.length-1, result, candidateCount * candidates[candidates.length-1]);
            if(!probeSuccess){
                break;
            }
        }
        return result;
    }

    private boolean probe(int[] candidates, int[] counts, int target, int increasingIndex, List<List<Integer>> result, int sum){
        if(sum > target){
            return false;
        }
        if(sum == target){
            result.add(getCandidatesWithCount(candidates, counts));
            return false;
        }
        if(increasingIndex == 0){
            return true;
        }
        int nextIncreasingIndex = increasingIndex-1;
        int temp = counts[nextIncreasingIndex];
        for(int candidateCount =0;;candidateCount++){
            counts[nextIncreasingIndex] = candidateCount;
            boolean probeSuccess = probe(candidates, counts, target,
                    nextIncreasingIndex, result, sum + candidateCount * candidates[nextIncreasingIndex]);
            if(!probeSuccess){
                break;
            }
        }
        counts[nextIncreasingIndex] = temp;
        return true;
    }

    private List<Integer> getCandidatesWithCount(int[] candidates, int[] counts){
        List<Integer> group = new ArrayList<>();
        for(int j = 0 ;j<counts.length; j++){
            for(int i = 0;i < counts[j];i++){
                group.add(candidates[j]);
            }
        }
        return group;
    }


    public void test() {
        int[] candidates = {2,3,5};
        List<List<Integer>> result = combinationSum(candidates, 8);
        return;
    }
}
